// 2025/3/2
// https://leetcode.cn/problems/find-all-anagrams-in-a-string/?envType=study-plan-v2&envId=top-100-liked
// 找到字符串中所有字母异位词

class Solution {
    public:
        vector<int> findAnagrams(string s, string p) {
            int m = s.size(), n = p.size();
            if(m < n) return {};
    
            vector<int> ans;
            string key(26, 0);
            string pkey(26, 0);
            for(int i = 0; i < n; i++) 
            {
                ++key[s[i] - 'a'];
                ++pkey[p[i] - 'a'];
            }
    
            if(key == pkey) ans.emplace_back(0);
            for(int i = 1; i < m - n + 1; i++)
            {
                --key[s[i - 1] - 'a'];
                ++key[s[i + n - 1] - 'a'];
                if(key == pkey) ans.emplace_back(i);
            }
    
            return ans;
        }
    };